// BinaryHeap.cpp: implementation of the CBinaryHeap class.
//
//////////////////////////////////////////////////////////////////////

#include "stdafx.h"
#include "BinaryHeap.h"

#ifdef _DEBUG
#undef THIS_FILE
static char THIS_FILE[]=__FILE__;
#define new DEBUG_NEW
#endif


CBinaryHeap::CBinaryHeap()
{
	memset(map,0,sizeof(map));
	this->pHeap=NULL;
	this->BHReset();
}

CBinaryHeap::~CBinaryHeap() 
{
	delete pHeap;
}

void CBinaryHeap::BHReset()
{
	count = 0 ;
	if ( pHeap == NULL )
		pHeap = new NODE[MAX_HEAP_LEN] ;
	else
		memset ( pHeap, 0, sizeof(pHeap) ) ;
}

bool CBinaryHeap::BHAddNew ( int x, int y, int value )
{
	NODE node ( x, y, value ) ;
	this->pHeap[this->count++] = node ;
	this->BHFilterUp ( this->count-1 ) ;
	return true ;
}

bool CBinaryHeap::BHDelTop ()
{
	if ( this->count <= 0 )
		return false ;
	
	this->count-- ;
	this->pHeap[0] = this->pHeap[this->count] ;
	this->BHFilterDown ( 0 ) ; 
}

bool CBinaryHeap::BHAdjustByIndex ( int index, int nNewValue )
{
	this->pHeap[index].value = nNewValue ;
	if ( this->BHFilterDown ( index ) == index )
		this->BHFilterUp ( index ) ;
	return true ;
}

int CBinaryHeap::BHGetNum ()
{
	return this->count ;
}

NODE& CBinaryHeap::BHGetTop ()
{
	return this->pHeap[0] ;
}

int CBinaryHeap::BHFilterDown ( int index )
{
	NODE TempNode = this->pHeap[index] ;
	int cur = index ;
	int son = 2 * cur + 1 ;
	while ( son < this->count )
	{
		if ( son+1 < this->count && this->pHeap[son].value > this->pHeap[son+1].value )
			son++ ;
		
		if ( TempNode.value < this->pHeap[son].value )
			break ;
		else
		{
			this->pHeap[cur] = this->pHeap[son] ;
			this->BHUpdatePos ( this->pHeap[son].x, this->pHeap[son].y, cur ) ;
			cur = son ;
			son = 2 * cur + 1 ;
		}
	}
	this->pHeap[cur] = TempNode ;
	this->BHUpdatePos ( TempNode.x, TempNode.y, son ) ;
	return son ; 
}

int CBinaryHeap::BHFilterUp ( int index )
{
	NODE TempNode = this->pHeap[index] ;
	int cur = index ;
	int parent = ( cur - 1 ) / 2 ;
	while ( cur != 0 )
	{
		if ( this->pHeap[parent].value <= TempNode.value )
			break ;
		
		this->pHeap[cur] = this->pHeap[parent] ;
		this->BHUpdatePos ( this->pHeap[parent].x, this->pHeap[parent].y, cur ) ;
		cur = parent ;
		parent = ( cur - 1 ) / 2 ;
	}
	this->pHeap[cur] = TempNode ;
	this->BHUpdatePos ( TempNode.x, TempNode.y, cur ) ;
	return cur ; 
}

void CBinaryHeap::BHUpdatePos( int x, int y, int pos)
{
	map[x][y].index =pos;
}